#include<iostream>
#include<algorithm>
using namespace std;

int find_max(int n[])
{
	int len = sizeof(n);
	int tmp = n[0];
	int tmp_pointer = 0;
	for (int i = 1; i < len; i++)
	{
		if (n[i] > tmp)
		{
			tmp = n[i];
			tmp_pointer = i;
		}

	}
	return tmp_pointer;
}


int BestValue(int row[], int col[], int n)
{
	;
	int num_tmp = 1;
	if (row == NULL || col == NULL || n <= 0)
	{
		cout << "error" << endl;
		exit(-1);
	}
	if (n == 1)
	{
		return 0;
	}
	if (n == 2)
	{
		int tmp = row[0] * row[1] * col[1];
		return tmp;
	}
	else//找到划分点
	{
		int i = 0;
		int sub_row[100] = { 0 }, sub_col[100] = { 0 }, n_new = n - 1;
		
		int npp = find_max(row);

		sub_row[0] = row[0];
		for (int tmp=0; i < n-1; i++)
		{
			if (i+1 == npp)continue;
			else
			{
				sub_col[tmp] = col[i];
				sub_row[tmp + 1] = row[i + 1];
				tmp++;
			}

		}
		sub_col[n - 2] = col[n - 1];
		
		int answer;
		answer = BestValue(sub_row,sub_col,n_new) + row[npp - 1] * col[npp] * row[npp];
		return answer;
	}
}
/*
* int main()
{
	int r[4] = { 1,2,4,1 };
	int c[4] = { 2,4,1,3 };
	int n = 4;
	int p;
	p = BestValue(r, c, n);
	return p;
}
*/
 int main()
{
	 int r[10] = { 1,2,4,1,9,34,12,55,30,12 };
	 int c[10] = { 2,4,1,9,34,12,55,30,12,9 };
	int n = 10;
	int p;
	p = BestValue(r, c, n);
	return p;
}